package leetcode.map;

import java.util.*;

public class Lc802 {

    public List<Integer> eventualSafeNodes(int[][] graph) {

        HashMap<Integer, HashSet> pre = new HashMap<>(); //记录每个点的前驱节点集合
        int[] outdgree = new int[graph.length];
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return outdgree[o1] - outdgree[o2];
            }
        });
        for (int i = 0; i < graph.length; i++) {
            outdgree[i] = graph[i].length;
            if (outdgree[i] == 0) pq.offer(i);
            for (int x : graph[i]) {
                HashSet<Integer> s2 = pre.getOrDefault(x, new HashSet<Integer>());
                s2.add(i);
                pre.put(x, s2);
            }
        }
        ArrayList<Integer> ans = new ArrayList<>();
        while (!pq.isEmpty()) {
            int cur = pq.poll();
            ans.add(cur);
            HashSet<Integer> preNodeSet = pre.get(cur);
            if (preNodeSet == null) continue;
            for (Integer node : preNodeSet) {
                outdgree[node]--;
                if (outdgree[node] == 0) {
                    pq.offer(node); //出度为0，即为安全节点，再放入队列，将其前驱的出度逐个减去
                }
            }
        }
        Collections.sort(ans);
        return ans;
    }

    public static void main(String[] args) {
        ArrayList<Integer> a = new ArrayList<>();
        a.add(1);
        a.remove(Integer.valueOf(1));
        System.out.println(a.size());
    }


}
